import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

/**
* @description: 802. 找到最终的安全状态
* @author hewei
* @date 2022/8/27 16:21
* @version 1.0
*/

public class EventualSafeNodes {

    HashSet<Integer> good;
    HashSet<Integer> bad;
    int[][] graph;
    public List<Integer> eventualSafeNodes1(int[][] graph) {
        this.graph = graph;
        good = new HashSet<>();
        bad = new HashSet<>();
        for (int i = 0; i < graph.length; i++) {
            if (good.contains(i) || bad.contains(i)) continue;
            HashSet<Integer> set1 = new HashSet<>();
            HashSet<Integer> set2 = new HashSet<>();
            process(i, set1, set2);
            good.addAll(set2);
            bad.addAll(set1);
        }
        List<Integer> ans = new ArrayList<>(good);
        Collections.sort(ans);
        return ans;
    }

    public boolean process(int i, HashSet<Integer> setBad, HashSet<Integer> setGood) {
        if (good.contains(i)) return true;
        if (bad.contains(i)) return false;
        if (setBad.contains(i)) return false;
        if (setGood.contains(i)) return true;
        setBad.add(i);
        for (int a : graph[i]) {
            if (!process(a, setBad, setGood)) return false;
        }
        setBad.remove(i);
        setGood.add(i);
        return true;
    }

    int[] color;
    public List<Integer> eventualSafeNodes(int[][] graph) {
        this.graph = graph;
        color = new int[graph.length];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) {
            if (dfs(i)) ans.add(i);
        }
        return ans;
    }

    public boolean dfs(int i) {
        if (color[i] != 0) return color[i] == 2;

        color[i] = 1;
        for (int a : graph[i]) {
            if (!dfs(a)) return false;
        }
        color[i] = 2;
        return true;
    }
}
